package DataStructure.array.swordOffer2;

/**
 * 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
 * 题目简述：调整一个数组中的数字，使所有奇数在前半部分，所有偶数在后半部分
 */
public class Exchange {

    public static void main(String[] args) {
        new Exchange().exchange(new int[]{2,16,3,5,13,1,16,1,12,18,11,8,11,11,5,1});
    }
    /**
     * 定义区间[0, low)为奇数区间，(high, length-1]为偶数区间。当low <= high时循环：
     *  - 向右拓展奇数区间边界直到越过high边界或者遇到偶数
     *  - 向左拓展偶数区间边界直到越过low边界或者遇到奇数
     *  - 扫描后若low < high则说明low指向了偶数 high指向了奇数，因此交换 然后再向中间递增指针
     */
    public int[] exchange(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            //向右拓展奇数区间边界直到越过high边界或者遇到偶数
            while (low <= high && nums[low] % 2 == 1)
                low++;
            //向左拓展偶数区间边界直到越过low边界或者遇到奇数
            while (low <= high && nums[high] % 2 == 0)
                high--;
            //此时若low < high则说明low指向了偶数 high指向了奇数，因此交换 然后再向中间递增指针
            if (low < high) {
                int t = nums[low];
                nums[low++] = nums[high];
                nums[high--] = t;
            }
        }
        return nums;
    }
}
